import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution1224 {
    public int maxEqualFreq(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }
        PriorityQueue<int[]> queue1=new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        PriorityQueue<int[]> queue2=new PriorityQueue<>((a,b)->b[1]-a[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue1.add(new int[]{entry.getKey(),entry.getValue()});
            queue2.add(new int[]{entry.getKey(),entry.getValue()});
        }
        int start=0;
        while (start<nums.length-1 && nums[start]==nums[start+1]){
            start++;
        }
        for (int i=nums.length-1;i>=start+1;i--){
            clear(queue1,map);
            if (queue1.peek()[1]==1){
                int[] t=queue1.poll();
                clear(queue1,map);
                clear(queue2,map);
                if (queue1.peek()[1]==queue2.peek()[1]){
                    return i+1;
                }else {
                    queue1.add(t);
                }
            }
            clear(queue2,map);
            int[] t=queue2.poll();
            clear(queue1,map);
            clear(queue2,map);
            if (queue1.peek()[1]==queue2.peek()[1] && queue1.peek()[1]==t[1]-1){
                return i+1;
            }else {
                queue2.add(t);
            }
            map.put(nums[i],map.get(nums[i])-1);
            if (map.get(nums[i])==0){
                map.remove(nums[i]);
            }else {
                queue1.add(new int[]{nums[i],map.get(nums[i])});
                queue2.add(new int[]{nums[i],map.get(nums[i])});
            }
        }
        return start+1;
    }

    private void clear(PriorityQueue<int[]> queue, Map<Integer, Integer> map) {
        while (!queue.isEmpty() && (!map.containsKey(queue.peek()[0]) || queue.peek()[1]!=map.get(queue.peek()[0]))){
            queue.poll();
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1224().maxEqualFreq(new int[]{1,1,1,2,2,2,3,3,3,4,4,4,5}));
    }
}
